package org.aplombh.java.awcing.basic.struct.heap;

import org.aplombh.java.utils.SwapUtils;

import java.util.Objects;
import java.util.Scanner;

/**
 * 维护一个集合，初始时集合为空，支持如下几种操作：
 * <p>
 * I x，插入一个数 x；
 * PM，输出当前集合中的最小值；
 * DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
 * D k，删除第 k 个插入的数；
 * C k x，修改第 k 个插入的数，将其变为 x；
 * 现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
 * <p>
 * 输入格式
 * 第一行包含整数 N。
 * <p>
 * 接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
 * <p>
 * 输出格式
 * 对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
 * <p>
 * 每个结果占一行。
 * <p>
 * 数据范围
 * 1≤N≤105
 * −109≤x≤109
 * 数据保证合法。
 * <p>
 * 输入样例：
 * 8
 * I -10
 * PM
 * I -10
 * D 1
 * C 2 8
 * I 6
 * PM
 * DM
 * 输出样例：
 * -10
 * 6
 */
public class Heap_839 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = 0;

        Heap heap = new Heap();

        int k, x;
        while (n-- != 0) {

            String op = scanner.next();

            if (Objects.equals(op, "I")) {
                x = scanner.nextInt();
                heap.h[++heap.tsize] = x;
                heap.ph[++m] = heap.tsize;
                heap.hp[heap.tsize] = m;
                heap.up(heap.tsize);
            } else if (Objects.equals(op, "PM")) {
                System.out.println(heap.h[1]);
            } else if (Objects.equals(op, "DM")) {
                heap.heap_swap(1, heap.tsize--);
                heap.down(1);
            } else if (Objects.equals(op, "D")) {
                k = scanner.nextInt();
                k = heap.ph[k];
                heap.heap_swap(k, heap.tsize--);
                heap.down(k);
                heap.up(k);
            } else {
                k = scanner.nextInt();
                x = scanner.nextInt();
                k = heap.ph[k];
                heap.h[k] = x;
                heap.down(k);
                heap.up(k);
            }
        }
    }
}

/**
 * 不太懂
 * not quite understand
 */

// TODO
class Heap {
    private static final int N = 100010;

    int[] h, ph, hp;
    int tsize;

    Heap(){
        h = new int[N];
        ph = new int[N];
        hp = new int[N];
    }


    void heap_swap(int t, int u) {
//        swap(ph[hp[t]], ph[hp[u]]);
        SwapUtils.swap(hp[t], hp[u], ph);
//        swap(hp[t], hp[u]);
        SwapUtils.swap(t, u, hp);
//        swap(h[t], h[u]);
        SwapUtils.swap(t, u, h);
    }

    void down(int u) {
        int t = u;
        if (u * 2 <= tsize && h[u * 2] < h[t]) t = u * 2;
        if (u * 2 + 1 <= tsize && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        if (u != t) {
            heap_swap(t, u);
            down(t);
        }
    }

    void up(int u) {
        while (u / 2 != 0 && h[u / 2] > h[u]) {
            heap_swap(u / 2, u);
            u /= 2;
        }
    }
}